
 //Definition for a binary tree node.

 import java.util.LinkedList;
 import java.util.List;
 import java.util.Queue;

 class Solution1 {
    public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null&&q==null){
            return true;
        }else if(p==null || q==null){
            return false;
        }else if(p.val!=q.val){
            return false;
        }else{
            return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
        }
    }
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        //1.判断两棵树是不是两颗相同的树
        if(root==null||subRoot==null){
            return false;
        }
        if(isSameTree(root,subRoot))
            return true;
        //2.SubRoot是不是root.left的子树
        if(isSubtree(root.left,subRoot))
            return true;
        //3.SubRoot是不是root.right的子树
        if(isSubtree(root.right,subRoot))
            return true;
        return false;
    }
    public boolean isBalanced(TreeNode root) {
        if(root==null) return true;
        int leftH=heightBinary(root.left);
        int rightH=heightBinary(root.right);
        return Math.abs(leftH-rightH)<2&&isBalanced(root.right)&&isBalanced(root.left);

    }
    public int heightBinary(TreeNode root){
        if(root==null){
            return 0;
        }
        else{
            return Math.max(heightBinary(root.left),heightBinary(root.right))+1;
        }
    }
    public boolean isSymmetric(TreeNode root) {
        if(root==null){
            return true;
        }
        return isSymmetricChild(root.left,root.right);
    }
    public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree){
        if(leftTree==null&&rightTree==null){
            return true;
        }
        if((leftTree==null&&rightTree!=null)||(rightTree==null&&leftTree!=null)){
            return false;
        }
        if(leftTree.val!=rightTree.val){
            return false;
        }
        return isSymmetricChild(leftTree.left,rightTree.right)&&isSymmetricChild(rightTree.left,leftTree.right);
    }


    public void levelOrder(TreeNode root) {
        if(root==null){
            return;
        }
        Queue<TreeNode>qu=new LinkedList<>();
        qu.offer(root);
        while(!qu.isEmpty()){
            TreeNode cur=qu.poll();
            System.out.println(cur.val);
            if(cur.left!=null){
                qu.offer(cur.left);
            }
            if(cur.right!=null){
                qu.offer(cur.right);
            }
        }

    }
}